package day01;

/**
 * @author Jetwang
 * @version 1.0
 * @since 2023/3/11 22:23
 * 矩阵中的路径
 */
public class Offer12Non {
    int n;
    int m;
    int len;
    boolean[][] visited;
    public boolean exist(char[][] board, String word) {
        this.n = board.length;
        this.m = board[0].length;
        this.len = word.length();
        this.visited = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (dsf(board, i, j, word, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    boolean dsf(char[][] board, int i, int j, String word, int k) {
        // 判断是否越界，已经访问过或者不匹配
        if(i < 0 || i >= n || j < 0 || j >= m || board[i][j] != word.charAt(k)) {
            return false;
        }

        if(k == len - 1){
            return true;
        }
        //visited[i][j] = true;
        board[i][j] = '\n';
        // 四个方向都搜索一下
        boolean res = dsf(board, i, j + 1, word, k + 1) ||
                dsf(board, i + 1, j, word, k + 1) ||
                dsf(board, i, j - 1, word, k + 1) ||
                dsf(board, i - 1, j, word, k + 1);

        board[i][j] = word.charAt(k);
        return res;
    }
}
